package org.labuladong.动态规划算法.DP;

/**
 * @Auther: qingle
 * @Date: 2024/10/23-11:21
 * @Description: 超出时间限制
 * 15 / 189 个通过的测试用例
 *
 * @version: 1.0
 */
public class dp02_coins_bl {

	public static int coinChange(int[] coins, int amount) {

		return dp(coins, amount);
	}

	private static int dp(int[] coins, int amount) {

		if(amount==0) return 0; //
		if(amount<0) return -1; // 没找到
		int res = Integer.MAX_VALUE;

		for (int i = 0; i < coins.length; i++) {
			int sub = dp(coins, amount-coins[i]);
			if(sub==-1) continue;
			res = Math.min(res, sub+1);
		}
		return res==Integer.MAX_VALUE?-1:res; // 值没变，说明没找到
	}


	public static void main(String[] args) {

		int[] coins = {1,2,5};
		int amount = 11;
		System.out.println(coinChange(coins, amount));
	}
}
